/*
 * scanner that tokenizes the input
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SYMBOL_SIZE 80
#define LINE_CHARS 800
#define MAX_LINES 800

int handle_left_recursion(char *, char *);
void remove_left_recursion();
void remove_common_prefix();
char *fix_prefix(char *, char *, char *, char *);

char *output_buffer; // big buffer for all lines that are being parsed, and will be printed
char *new_non_terminal;
FILE *input_file;
FILE *output_file;

main() {

remove_left_recursion();
remove_common_prefix();

}

/*
 * Takes in the assigned variable, the token they have in common, and the rule that was entered,
 * it will then take and modify the string to remove the common prefix, and return a pointer to
 * a string which can then be split into 2 by delimiting newlines. The first string should be prefix-free
 * and the second one may need further parsing.
 */

char *fix_prefix(char *start_variable, char *common_symbol, char* current_line, char* token_list) {

char var_one[SYMBOL_SIZE];
char var_two[SYMBOL_SIZE];
char temp_symbol[SYMBOL_SIZE];
char first_line[LINE_CHARS];
char second_line[LINE_CHARS];
char temp_line[LINE_CHARS];
char temp_token[LINE_CHARS];
char *token; 
char *symbol;
char **line_ptr;
char **token_ptr;
char **initial_split_ptr;

int len;
strcpy(var_one,start_variable);
strcpy(var_two,start_variable);

len = strlen(var_two);
var_two[len-2] = '\'';
var_two[len - 1] = '>';
var_two[len] = '\0';

if (strstr(token_list,var_two) == NULL ) { // append the new token if it isn't there already
	sprintf(temp_symbol, " %s", var_two);
	strcat(token_list, temp_symbol);
}


line_ptr = malloc(sizeof(char * ));
token_ptr = malloc(sizeof(char * ));
initial_split_ptr = malloc(sizeof(char * ));

//puts(current_line);

// a fixed line
sprintf(first_line, "%s: %s %s", var_one, common_symbol, var_two);

// produce the line that may not be done
sprintf(second_line, "%s : ", var_two);

token = strtok_r(current_line,":", initial_split_ptr); // split the orginal line
token = strtok_r(NULL,":", initial_split_ptr); // get the right half
strcpy(temp_line, token); // store it in temp_line 

// retokenize the line by "|"
token = strtok_r(temp_line, "|", line_ptr);

while (token != NULL) {
	strcpy(temp_token, token);
	// tokenize with spaces
	symbol = strtok_r(temp_token," ", token_ptr); // eat the first token
	while (symbol != NULL) {
		symbol = strtok_r(NULL," ", token_ptr); // get next token
		if (symbol != NULL) {
			sprintf(temp_symbol, "%s ", symbol);
			strcat(second_line, temp_symbol);
		}
	}
	token = strtok_r(NULL, "|", line_ptr); // grab the next token

	if (token != NULL) { // if it wasn't the last token
		sprintf(temp_symbol, "| ", symbol);
		strcat(second_line, temp_symbol);
	} else { // if it was the last item, end the line
		sprintf(temp_symbol, "\n", symbol);
		strcat(second_line, temp_symbol);
	}
}
// both strings are made now, so modify the input string
sprintf(current_line, "%s\n", first_line); // this blanks it
strcat(current_line, second_line); // this appends
//sprintf(temp_symbol, "\n");
//strcat(current_line, temp_symbol);

free(line_ptr);
free(token_ptr);
free(initial_split_ptr);

}

/*
 * searches for common prefixes in the string, and replaces any it finds
 */
void remove_common_prefix() {
// variable declarations
char tmp[50];
char *fn = "original_grammar";
char *string;
char *current_line;
size_t size;
int bytes_read;
// strings for the first 4 lines
char *token_line_original; // used to hold the tokens
char *nonterminals_to_add;
char *non_terminal_line; // used to add new terminals
char *start_line;
char *rules_line;

// open the relevant files
sprintf(tmp, "%s%s", fn, "_no_LR.txt");
input_file = fopen(tmp, "r");
sprintf(tmp, "%s%s", fn, "_no_LR_or_CP.txt");
output_file = fopen(tmp, "w");

size = sizeof(char)*LINE_CHARS; // a default value for a "line" of text

// malloc the strings
string = (char *) malloc (size);
current_line = (char *) malloc (size);
output_buffer = malloc(sizeof(char) * LINE_CHARS * MAX_LINES);

// malloc for the first 4 lines
token_line_original = (char *) malloc (size);
nonterminals_to_add = (char *) malloc (size);
non_terminal_line = (char *) malloc (size);
start_line = (char *) malloc (size);
rules_line = (char *) malloc (size);

// start reading in the first 4 lines of the file
bytes_read = getline(&string, &size, input_file); // reads tokens
strcpy(token_line_original, string);

bytes_read = getline(&string, &size, input_file); // reads non-terminals
strncpy(non_terminal_line, string, size);

bytes_read = getline(&string, &size, input_file); // reads %Start line
strncpy(start_line, string, size);

bytes_read = getline(&string, &size, input_file); // reads %Rules line
strncpy(rules_line, string, size);

bytes_read = getline(&string, &size, input_file); // read first real line
current_line = strncpy(current_line, string, size);

begin:
while (bytes_read != -1) { // parse the file line-by-line
	const char *delimiters = ":|";
	int common_substring = 1;		
	int first;
	int token_num;
	char *current_token;
	char *token_piece;
	char *return_val;
	char **pristine_ptr;
	char common_symbol[SYMBOL_SIZE];
	char start_variable[SYMBOL_SIZE];
	char pristine_token[LINE_CHARS];
	char temp_buffer[LINE_CHARS];
	//char token_piece[SYMBOL_SIZE];
	
	scan:
	return_val = malloc(sizeof(char **));	
	//puts(token_line_original);
	

	//puts("start");
	pristine_ptr = malloc(sizeof(char**));
	strcpy(pristine_token, string);
	current_token = strtok_r(pristine_token, ":", pristine_ptr); // get the left hand side
	current_token = strtok_r(NULL, ":", pristine_ptr); 
	strcpy(pristine_token,current_token);
	
	//puts(string);
	current_token = strtok_r(string, delimiters, &return_val); // get the first real token
	strcpy(start_variable, current_token); // keep the current variable
	current_token = strtok_r(NULL, delimiters, &return_val); // get the first real token
	
	first = 1; // first time for this looping
	token_num = 0;
	while(current_token != NULL) { // go through all of the "tokens" on this line
		token_piece = strtok(current_token, " ");
		//puts(token_piece);
		if (first == 1) {
			strcpy(common_symbol, token_piece);
			first = 0;
		} else {
			if (strcmp(token_piece,common_symbol) == 0) {
				// do nothing
			} else {
				common_substring = 0; // mark that they don't all have a common substring
			}
		}
		//puts(current_token);
		current_token = strtok_r(NULL, delimiters, &return_val); // get the first real token
		token_num++;

	}
	if (common_substring == 0 || token_num < 2) { // there was no common substring
		// do nothing to the string, but print to the buffer and end
		current_line = strncpy(current_line, string, size);
		sprintf(temp_buffer, "%s: %s", start_variable, pristine_token);
		output_buffer = strcat(output_buffer, temp_buffer); // copy the normal one since no more prefixes 
		if (bytes_read == -1) { // end when all strings have been read
			//puts("end");
		} else { // read more strings
			bytes_read = getline(&string, &size, input_file); // read next line
			if (bytes_read != -1) {
				current_line = strncpy(current_line, string, size);
			}
			goto begin;
		}		
	} else { // there was a common substring so fix it and rescan the new string
		char **parse_ptr;
		char *first_line;
		char newline[SYMBOL_SIZE];
		fix_prefix(start_variable ,common_symbol, current_line, nonterminals_to_add);
		
		parse_ptr = malloc(sizeof(char **));
		first_line = strtok_r(current_line, "\n", parse_ptr);
		strcat(output_buffer, first_line); // add the now complete line
		sprintf(newline,"\n"); // add a newline
		strcat(output_buffer, newline);
		first_line = strtok_r(NULL, "\n", parse_ptr); // get the possibly incomplete line
		strcpy(string, first_line); //set string to our newly created line
		strcpy(current_line, first_line); //set current_line to our newly created line
		strcat(string, newline);
		strcat(current_line, newline);
		free(parse_ptr);
		goto scan; // start over again
	}
}

end:
if (0) { // purely so that the end label can associate with a statement
// do nothing
}

int len;
char newline[SYMBOL_SIZE];
sprintf(newline, "\n");
strcat(nonterminals_to_add, newline);
len = strlen(non_terminal_line);
non_terminal_line[len - 1] = '\0'; // overwrite the newline
strcat(non_terminal_line, nonterminals_to_add);

fprintf(output_file,"%s",token_line_original);
//puts(token_line);
fprintf(output_file,"%s",non_terminal_line);
fprintf(output_file,"%s",start_line);
fprintf(output_file,"%s",rules_line);
fprintf(output_file,"%s",output_buffer);

fclose(output_file);
fclose(input_file);

//free((char *) output_buffer);
//free(string);
//free(current_line);
//free(token_line);
//free(non_terminal_line);
//free(start_line);
//free(rules_line);
}

/*
 * Parses the file looking for instances of left recursion, and when it
 * finds them, calls handle_left_recursion to deal with them. After it 
 * runs it creates a file containing the modified grammar with no left
 * recursion (no LR)
 */
void remove_left_recursion () {
char tmp[50];
//char *fn = "test_grammar";
char *fn = "original_grammar";
char *string;
char *whole_line;
char *rules_line;
char *start_line;
char *token_line; // used to add new tokens
char *non_terminal_line; // used to add new terminals
size_t size;
int bytes_read;

sprintf(tmp, "%s%s", fn, ".txt");
input_file = fopen(tmp, "r");
sprintf(tmp, "%s%s", fn, "_no_LR.txt");
output_file = fopen(tmp, "w");


size = sizeof(char)*LINE_CHARS; // default value

output_buffer = (char *) malloc (size * MAX_LINES); //assuming no more than 200 lines of output rules 

string = (char *) malloc (size);
token_line = (char *) malloc (size);
non_terminal_line = (char *) malloc (size);
rules_line = (char *) malloc (size);
start_line = (char *) malloc (size);
whole_line = (char *) malloc (size);
new_non_terminal = (char *) malloc (size); // holds new states we add

bytes_read = getline(&string, &size, input_file); // reads tokens
strncpy(token_line, string, size);
//fprintf(output_file, string);


bytes_read = getline(&string, &size, input_file); // reads non-terminals
strncpy(non_terminal_line, string, size);
//fprintf(output_file, string);

bytes_read = getline(&string, &size, input_file); // reads %Start line
strncpy(start_line, string, size);

bytes_read = getline(&string, &size, input_file); // reads %Rules line
strncpy(rules_line, string, size);

int left_recurse; // keep track of if there was left recursion
while (bytes_read != -1) { 
	char *first;
	char *temp;
	char revised_line;
	char new_line;
	int first_symbol = 1;
	left_recurse = 0; // set to 0 every loop

	bytes_read = getline(&string, &size, input_file); // get first line
	
	if (bytes_read == -1) { // if we are out of lines
		break; // leave loop
	}

	strncpy(whole_line, string, size); // copy it into whole_line
	temp = strtok(string," "); // read in first token (non-terminal)
	first = temp;
	temp = strtok(NULL, " "); // read in ":"
	
	// checks for left recursion
	// on the ":" character
	while (temp != NULL) {
		temp = strtok(NULL, " "); // read in first "real" character
		if (temp != NULL) {
			//puts(temp);
		}

		if (temp != NULL && first_symbol == 1 && strcmp(temp, first) == 0) { // if its left recursive
			if (left_recurse == 0) { // only call it once
				char *temp_symbol;
				int len;
				if (strstr(token_line,"EMPTY") == NULL) { // only attach once
					temp_symbol = " EMPTY\n"; // for tacking on the empty state
					len = strlen(token_line);
					token_line[len-1] = '\0'; // overwrite newline
					strcat(token_line, temp_symbol);
				}
				if(handle_left_recursion(first, whole_line) == 0) { // catch errors
					// do nothing
				} else {
					exit(0);
				}
			}
			//puts("set var");
			left_recurse = 1;
			// rewrite it 
		}
		
		if (temp != NULL && strcmp(temp,"|") == 0) { // reset if its an "|" char
			first_symbol = 1;
		} else { // else make sure we know it can't be left recursive
			first_symbol = 0;
		}
	}
	if (left_recurse == 0) { // didn't recurse
		char endline[SYMBOL_SIZE];
		strcat(output_buffer,whole_line);
		sprintf(endline, "\0");
		strcat(output_buffer,endline);
	} else {
		//puts("no recurs");
	}
	//bytes_read = getline(&string, &size, input_file); // get first line
	//puts(string);
}

// add the new terminals
int len;
char *newline;
len = strlen(non_terminal_line);
non_terminal_line[len-1] = '\0'; // overwrite newline
strcat(non_terminal_line, new_non_terminal);
newline = "\n";
strcat(non_terminal_line, newline);

int ret;

// writes out the new file
fprintf(output_file,"%s",token_line);
fprintf(output_file,"%s",non_terminal_line);
fprintf(output_file,"%s",start_line);
fprintf(output_file,"%s",rules_line);
fprintf(output_file,"%s",output_buffer);

fflush(output_file);

fclose(output_file);
fclose(input_file);
// frees up the malloc'd space
//free(string);
//free(token_line);
//free(non_terminal_line);
//free(start_line);
//free(rules_line);
//free(whole_line);
//free(output_buffer);

return;
}

int handle_left_recursion(char *symbol, char *line) {
	char *token;
	char line_one[LINE_CHARS];
	char line_two[LINE_CHARS];
	char line_buff[LINE_CHARS];
	char temp_symbol[SYMBOL_SIZE];
	char symbol_one[SYMBOL_SIZE];
	char symbol_two[SYMBOL_SIZE];
	int L1_first = 1;
	int L2_first = 1;
	int length;
	int end_in_epsilon = 0;

	const char delimiters[] =" \n"; // break on space or newline

	// inital setup of symbols for rules
	length = strlen(symbol);
	strncpy(symbol_one, symbol, length); // remove the ">"
	symbol_one[length] = '\0';
	strncpy(symbol_two, symbol, length - 1); // remove the ">"
	symbol_two[length-1] = '\'';
	symbol_two[length] = '>';
	symbol_two[length + 1] = '\0';
	sprintf(line_one,"%s : ", symbol_one);
	sprintf(line_two,"%s : ", symbol_two);
	
	// this is used to keep track of new symbols we add 
	sprintf(temp_symbol, " %s", symbol_two);
	strcat(new_non_terminal, temp_symbol);

	// start getting tokens
	token = strtok(line, delimiters); // ignore the first
	token = strtok(NULL, delimiters); // ignore the second
	
	token = strtok(NULL, delimiters); // read in first "real" character
	while (token != NULL) {
		//puts(token);
		if (strcmp(token, &symbol_one[0]) == 0) { // if the token is the recursing one
			//puts("recursive");
			if (L2_first == 1) {
				// don't do put a "|" on the first one
				L2_first = 0;
			} else {
				sprintf(temp_symbol, "| "); // get ready to  write the symbol to the second line (exp')
				strcat(line_two, temp_symbol); 
			}
			token = strtok(NULL, delimiters); // skip the part thats being recursed on

			while (token != NULL && strcmp(token, "|") != 0) {
				//puts(token);
				sprintf(temp_symbol, "%s ",token); // get ready to  write the symbol to the second line (exp')
				strcat(line_two, temp_symbol); 
				token = strtok(NULL, delimiters); // read next token
			}

			sprintf(temp_symbol, "%s ", symbol_two); // add the "exp'"
			strcat(line_two, temp_symbol); 
			if (token != NULL) { // it must be "|"
				token = strtok(NULL, delimiters); // get past the "|"
			} else { // if null
				// do nothing
			}
			//puts("end recursive");
			
		} else {
			//puts("non recursive");
			end_in_epsilon = 1; // signals that there is an empty state in string 2
			if (L1_first == 1) {
				// don't do put a "|" on the first one
				L1_first = 0;
			} else {
				sprintf(temp_symbol, "| "); // get ready to  write the symbol to the second line (exp')
				strcat(line_two, temp_symbol); 
			}
			while (token != NULL && strcmp(token, "|") != 0) {
				sprintf(temp_symbol, "%s ",token); // get ready to write the token
				strcat(line_one, temp_symbol); 	
				token = strtok(NULL, delimiters); // read next token
			}
			sprintf(temp_symbol, "%s ", symbol_two);
			strcat(line_one, temp_symbol); // add the "exp"
			if (token != NULL) {
				token = strtok(NULL, delimiters); // get past the "|"
			} else { // read next token
				// do nothing
			}
			//puts("end non recursive");
		}
	}
	if (end_in_epsilon) {
		sprintf(temp_symbol, "| EMPTY");
		strcat(line_two, temp_symbol); // add the epsilon symbol
	} else {
		puts("Invalid rule, left recursion cannot be removed!");
		return(1);
	}
		
	sprintf(line_buff,"%s\n",line_one);
	strcat(output_buffer,line_buff);
	sprintf(line_buff,"%s\n",line_two);
	//puts(temp_symbol);
	//puts(line_two);
	strcat(output_buffer,line_buff);
	//puts(output_buffer);
	return(0);
}

